import random


# 380. O(1) 时间插入、删除和获取随机元素
# 使用 map 可以达到 O(1) 的时间复杂度
class RandomizedSet(object):

    def __init__(self):
        self.dict_ = {}

    def insert(self, val):
        """
        :type val: int
        :rtype: bool
        """
        if val in self.dict_:
            return False
        else:
            self.dict_[val] = None
            return True

    def remove(self, val):
        """
        :type val: int
        :rtype: bool
        """
        if val in self.dict_:
            self.dict_.pop(val)
            return True
        else:
            return False

    def getRandom(self):
        """
        :rtype: int
        """
        if not self.dict_:
            return None

        return random.sample(self.dict_.keys(), 1)[0]


# Your RandomizedSet object will be instantiated and called as such:
obj = RandomizedSet()
param_1 = obj.insert(1)
param_2 = obj.insert(2)
param_3 = obj.insert(2)
param_4 = obj.insert(3)
param_5 = obj.insert(4)
param_6 = obj.insert(5)
param_7 = obj.remove(2)
param_8 = obj.remove(2)
param_9 = obj.getRandom()
print(f"param_1:{param_1},param_2:{param_2},param_3:{param_3},"
      f"param_4:{param_4},param_5:{param_5},param_6:{param_6},"
      f"param_7:{param_7},param_8:{param_8},param_9:{param_9},")
